#include <bits/stdc++.h>
// 2025/01/23
// tag: 
// Author: Zhang Muen
using namespace std;

bool unsafe[401][401], vis[401][401], safe[401][401];
int m;
unordered_map<int, vector<pair<int, int>>> star;

void init(){
    for (auto x: star){
        for (auto i : x.second){
            safe[i.first][i.second] = true;
            if (i.first > 0)
                safe[i.first - 1][i.second] = true;
            if (i.first < 300)
                safe[i.first + 1][i.second] = true;
            if (i.second > 0)
                safe[i.first][i.second - 1] = true;
            if (i.second < 300)
                safe[i.first][i.second + 1] = true;
        }
    }
}

void meteor(int t){
    for (auto i : star[t]){
        unsafe[i.first][i.second] = true;
        if (i.first > 0)
            unsafe[i.first - 1][i.second] = true;
        if (i.first < 300)
            unsafe[i.first + 1][i.second] = true;
        if (i.second > 0)
            unsafe[i.first][i.second - 1] = true;
        if (i.second < 300)
            unsafe[i.first][i.second + 1] = true;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> m;
    for (int i = 1, t, a, b; i <= m; i++)
        cin >> a >> b >> t, star[t].push_back(make_pair(a, b));
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    vis[0][0] = true;
    int t = 0;
    init();
    while (!q.empty())
    {
        meteor(t);
        t++;
        int cnt = q.size();
        for (int i = 1; i <= cnt; i++){
            pair<int, int> now = q.front();
            int x = now.first, y = now.second;
            q.pop();
            if (!safe[x][y]){
                cout << t - 1;
                return 0;
            }
            if (unsafe[x][y])
                continue;
            if (x - 1 >= 0 && !vis[x - 1][y] &&!unsafe[x - 1][y])
                q.push(make_pair(x - 1, y)), vis[x - 1][y] = true;
            if (x + 1 <= 302 &&!vis[x + 1][y] &&!unsafe[x + 1][y])
                q.push(make_pair(x + 1, y)), vis[x + 1][y] = true;
            if (y - 1 >= 0 &&!vis[x][y - 1] &&!unsafe[x][y - 1])
                q.push(make_pair(x, y - 1)), vis[x][y - 1] = true;
            if (y + 1 <= 302 &&!vis[x][y + 1] &&!unsafe[x][y + 1])
                q.push(make_pair(x, y + 1)), vis[x][y + 1] = true;
        }
    }
    cout << -1;
    return 0;
}